// 题目描述
// 234. 回文链表
// 难度
// 简单
// 1747
// 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
//   示例 1：
// 输入：head = [1,2,2,1]
// 输出：true
// 示例 2：
// 输入：head = [1,2]
// 输出：false
//   提示：
// 链表中节点数目在范围[1, 105] 内
// 0 <= Node.val <= 9
//   进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
// 通过次数616,089提交次数1,153,919
// https://leetcode.cn/problems/palindrome-linked-list/

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

// 方法一 递归技巧（参考树的后序遍历）
function isPalindrome(head) {
  let left = head
  const helper = (head) => {
    if (!head) {
      return true
    }

    const res = helper(head.next) && (left.val === head.val)
    left = left.next

    return res
  }

  return helper(head)
}

// 方法二 双指针技巧
function isPalindrome1(head) {
  // 快慢指针模板
  let slow = head
  let fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }

  // fast 不空则链表节点为奇数
  // 向后移动一位
  if (fast) {
    slow = slow.next
  }

  const reverse = (head) => {
    if (head === null || head.next === null) {
      return head
    }

    const last = reverse(head.next)
    head.next.next = head
    head.next = null

    return last
  }

  // 代码执行到这里，slow 指向了链表正中间的下一位
  // 反转后面的链表
  let left = head
  let right = reverse(slow)
  while (right) {
    if (right.val !== left.val) {
      return false
    }
    left = left.next
    right = right.next
  }

  return true
}

const lst = new ListNode(1, new ListNode(3, new ListNode(1)))
console.log(
  isPalindrome1(lst)
)

